0662. 二叉树最大宽度【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS

1. 📝 题目描述

• leetcode

给你一棵二叉树的根节点 root，返回树的 最大宽度。

树的 最大宽度 是所有层中最大的 宽度。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

---

示例 1：

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2：

输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7)。

示例 3：

输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2)。

---

提示：

• 树中节点的数目范围是 [1, 3000]
• -100 <= Node.val <= 100

2. 🎯 s.1 - BFS

c

// 简化实现，使用 unsigned long long 避免溢出
typedef struct { struct TreeNode* node; unsigned long long idx; } Pair;

int widthOfBinaryTree(struct TreeNode* root) {
    Pair queue[3001];
    int head = 0, tail = 0;
    queue[tail++] = (Pair){root, 0};
    unsigned long long maxW = 0;
    while (head < tail) {
        int size = tail - head;
        unsigned long long first = queue[head].idx;
        for (int i = 0; i < size; i++) {
            Pair p = queue[head++];
            unsigned long long idx = p.idx - first;
            if (i == size - 1 && idx + 1 > maxW) maxW = idx + 1;
            if (p.node->left) queue[tail++] = (Pair){p.node->left, 2 * idx};
            if (p.node->right) queue[tail++] = (Pair){p.node->right, 2 * idx + 1};
        }
    }
    return (int)maxW;
}

js

/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function (root) {
  let maxW = 0n
  const queue = [[root, 0n]]
  while (queue.length) {
    const size = queue.length
    const first = queue[0][1]
    for (let i = 0; i < size; i++) {
      const [node, idx] = queue.shift()
      if (i === size - 1) {
        const w = idx - first + 1n
        if (w > maxW) maxW = w
      }
      if (node.left) queue.push([node.left, 2n * (idx - first)])
      if (node.right) queue.push([node.right, 2n * (idx - first) + 1n])
    }
  }
  return Number(maxW)
}

py

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        max_w = 0
        queue = deque([(root, 0)])
        while queue:
            size = len(queue)
            first = queue[0][1]
            for i in range(size):
                node, idx = queue.popleft()
                idx -= first
                if i == size - 1:
                    max_w = max(max_w, idx + 1)
                if node.left:
                    queue.append((node.left, 2 * idx))
                if node.right:
                    queue.append((node.right, 2 * idx + 1))
        return max_w

• 时间复杂度：$O(n)$，其中 n 是节点数
• 空间复杂度：$O(n)$

算法思路：

• BFS 遍历，每个节点带一个编号（左子节点 2*idx，右子节点 2*idx+1）
• 每层宽度 = 最右编号 - 最左编号 + 1
• 每层开始时减去最左编号防止溢出